iT邦幫忙

2024 iThome 鐵人賽

DAY 23
0
佛心分享-刷題不只是刷題

圖解LeetCode(入門篇)系列 第 23

圖解LeetCode(入門篇): 110. Balanced Binary Tree

  • 分享至 

  • xImage
  •  

110. Balanced Binary Tree

题目描述:

給定一個二元樹的根節點 root,判斷這棵樹是否是高度平衡的。

Example 1:
https://ithelp.ithome.com.tw/upload/images/20240901/20168306PulRuCe8qW.jpg

  • Input: root = [1,2,3,null,null,6,7]
  • Output: true

Example 2:
https://ithelp.ithome.com.tw/upload/images/20240901/20168306p191fxrNCM.jpg

  • Input: root = [1,2,3,null,null,6,7,null,null,null,9]
  • Output: false

解題思路:
高度平衡的二元樹是指一棵二元樹中,每個節點的左右兩個子樹的高度差的絕對值不超過 1。要判斷一棵二元樹是否是平衡的,我們可以使用遞迴的方法來檢查每個節點的左右子樹的高度差是否超過 1。如果某個節點的高度差超過 1,則這棵樹是不平衡的;如果不超過 1,則繼續遞迴檢查其左右子樹。

那麼,如何計算二元樹的高度呢?這個問題在 LeetCode 的 104. Maximum Depth of Binary Tree 中已經得到了答案。這裡,我們同樣採用遞迴法來求得二元樹的高度。通過遞迴遍歷每個節點,我們可以逐層計算樹的高度,並同時檢查是否符合高度平衡的條件。這樣,我們不僅能確定樹的高度,還能在計算過程中判斷樹是否平衡。
https://ithelp.ithome.com.tw/upload/images/20240901/20168306x9uZbR2Dw0.jpg

var isBalanced = function(root) {
    if (!root) return true;

    function helper(root) {
        if (!root) return 0;

        return 1 + Math.max(helper(root.left), helper(root.right));
    }

    const leftH = helper(root.left);
    const rightH = helper(root.right);

    if (Math.abs(leftH - rightH) > 1) return false;

    return isBalanced(root.left) && isBalanced(root.right);
};

時間複雜度:O(n*n),其中 n 是二元樹中的節點數。對於每個節點,我們都需要計算其左右子樹的高度,這樣的操作會導致對每個節點的高度計算重複多次,最壞情況下時間複雜度為 O(n*n)
空間複雜度:O(n),遞迴call stack的深度取決於樹的高度,最壞情況下棧的深度為 O(n)

上面的解法在時間複雜度上達到了 O(n*n),主要原因在於該解法是從根節點往下遞迴計算每個節點的高度,每當計算高度時都會再次遞迴,導致重複計算,從而使時間複雜度急劇增加。但是否有更好的方法來避免這種重複計算呢?答案是肯定的。

我們可以採用一種自底向上的遞迴方式來計算每個節點的高度。具體來說,從樹的葉子節點開始,逐層向上計算每個節點的高度。這樣,每個節點的高度只需要計算一次,從而避免了重複計算。通過這種方式,我們可以將時間複雜度大幅優化至 O(n)

這種自底向上的遞迴方法不僅提高了效率,還更適合處理樹的結構,特別是在需要頻繁計算樹高或檢查樹的平衡性時。這樣的優化能夠有效提升算法的性能,尤其是在處理大規模數據時更為顯著。
https://ithelp.ithome.com.tw/upload/images/20240901/2016830666fnrutnyg.jpg

var isBalanced = function(root) {
    function check(node) {
        if (!node) return 0;

        const leftHeight = check(node.left);
        if (leftHeight === -1) return -1;

        const rightHeight = check(node.right);
        if (rightHeight === -1) return -1;

        if (Math.abs(leftHeight - rightHeight) > 1) return -1;

        return 1 + Math.max(leftHeight, rightHeight);
    }

    return check(root) !== -1;
};

時間複雜度:O(n),其中 n 是二元樹中的節點數。每個節點只會被訪問一次,因此時間複雜度為 O(n)
空間複雜度:O(n),遞迴call stack的深度取決於樹的高度,最壞情況下棧的深度為 O(n)

總結:
這道題目可以歸類為「recursion」。從這題我們學習到,看似簡單的遞迴法其實蘊含著更深的思考。在一般情況下,二元樹的遞迴法通常是從根節點往下計算,這種方式直觀且容易學習,但它的缺點是需要多次計算子樹的高度,導致時間複雜度較高,在處理大規模樹結構時效率較低。

另一種更高效的遞迴方式是從葉子節點往上計算。通過自底向上計算,每個節點的高度只計算一次,並且在發現不平衡時可以立即停止遞迴,這樣優化了性能,特別適合處理大規模的二元樹。

這兩種遞迴方式各有優勢,建議讀者都要學習掌握,這樣在不同的情境下能夠靈活運用,選擇最適合的解題策略。


上一篇
圖解LeetCode(入門篇): 108. Convert Sorted Array to Binary Search Tree
下一篇
圖解LeetCode(入門篇): 111. Minimum Depth of Binary Tree
系列文
圖解LeetCode(入門篇)30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言